package apitest;

import java.util.Arrays;

/**
 * @Author liuhaoqi
 * @Date 2021/1/15 16:37
 * @Version 1.0
 */
public class test2 {
    public static void main(String[] args) {
        test2 test2 = new test2();
        int[] arr = {0,0,1,2,4,2,2,3,1,4};
        test2.getLeastNumbers(arr, 8);
    }

    public int[] getLeastNumbers(int[] arr, int k) {
        int[] ans = new int[k];

        //快排
        return quickSort(arr,0,arr.length-1,k-1);
    }

    public int[] quickSort(int[] nums,int low,int high,int k){
        // 每快排切分1次，找到排序后下标为j的元素，如果j恰好等于k就返回j以及j左边所有的数；
        int j = getPosition(nums, low, high);
        System.out.println(j);
        if (j == k) {
            return Arrays.copyOf(nums, j + 1);
        }
        // 否则根据下标j与k的大小关系来决定继续切分左段还是右段。
        return j > k? quickSort(nums, low, j - 1, k): quickSort(nums, j + 1, high, k);
    }

    public int getPosition(int[] arr,int low ,int high){
        int key = arr[low];
        System.out.println(low);
        while (low < high) {
            while (arr[high] >= key && high > low) {
                high--;
                System.out.println("!" + high);
            }
            arr[low] = arr[high];
            while (arr[low] <= key && low < high) {
                low++;
                System.out.println("!" + high+"!");
            }
            arr[high] = arr[low];
        }
        arr[low] = key;
        return low;
    }
}
